// 分治 - 归并
// 归并的核心思路就是先将数组分左右两块
// 再把左边数组排序，右边数组排序
// 再合并两个有序数组
// 类似于二叉树的后续遍历
// 典型的应用场景就是找逆序对 - 逆序对涉及到选择一左一右两个元素,这就是在合并两个有序数组涉及的操作,合并时统计逆序对数即可
// 找每个元素的逆序对的数量 - 关键的操作就是就是绑定 数组元素和下标 ,绑定方式就是新建一个同等规模的数组,同样进行归并排序的流程
// 找翻转对的个数 - 可以在合并两个有序之前找 翻转对 的个数，这个步骤可以使用双指针找
// 遇到复杂的归并题目，如果在合并两个有序数组这个步骤不好统计逆序对/翻转对，这个时候可以在合并之前完成这个操作，之后再合并

// 例题 4：
// 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
//
//        你需要返回给定数组中的重要翻转对的数量。
//
//        示例 1:
//
//        输入: [1,3,2,3,1]
//        输出: 2
//        示例 2:
//
//        输入: [2,4,3,5,1]
//        输出: 3
//        注意:
//
//        给定数组的长度不会超过50000。
//        输入数组中的所有数字都在32位整数的表示范围内。

// 解题思路:
// 数组分左右两块 - 递归排序
// 排序完成后，可以在两个有序数组中，使用双指针的方法找翻转对的个数
// 合并两个有序数组
// 还原数组

public class ReversePairs_2 {
    int ret = 0;
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        mergeSort(nums, 0, n - 1);
        return ret;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left; int cur2 = mid + 1;
        // 统计翻转对的个数
        while(cur1 <= mid && cur2 <= right){
            if((long)nums[cur1] > 2 * (long)nums[cur2]) {
                ret += (right - cur2 + 1);
                cur1++;
            }else cur2++;
        }
        cur1 = left; cur2 = mid + 1;
        int cur = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] < nums[cur2]) tmp[cur++] = nums[cur2++];
            else tmp[cur++] = nums[cur1++];
        }
        while(cur1 <= mid) tmp[cur++] = nums[cur1++];
        while(cur2 <= right) tmp[cur++] = nums[cur2++];
        for(int i = 0; i < right - left + 1; i++) nums[i + left] = tmp[i];
    }
}
